package JZOffer;

import 链表.easy.YiSiYi;

/**
 * @author Lw中
 * @date 2021/8/24 23:32
 */
public class Jz23 {

    // Jz23.链表中环的入口节点

    public class ListNode {
     int val;
     ListNode next;
     ListNode(int x) {
         val = x;
         next = null;
     }
    }

//    public ListNode detectCycle(ListNode head) {
//        if (!hasCycle(head)) return null;
//        int number = getNodeNumber(head);
//        if (number == 1) return null;
//        ListNode p1 = head;
//        ListNode p2 = head;
//        while (number > 0) {
//            p1 = p1.next;
//            number = number - 1;
//        }
//        while (p1 != p2) {
//            p1 = p1.next;
//            p2 = p2.next;
//        }
//        return p1;
//    }
//
//    public int getNodeNumber(ListNode head) {
//        ListNode fast = head;
//        ListNode low = head;
//        ListNode target = null;
//        while (fast != null && fast.next != null && fast.next.next != null) {
//            low = low.next;
//            fast = fast.next.next;
//            if (low == fast) {
//                target = fast; break;
//            }
//        }
//        int i = 1;
//        ListNode node = target;
//        while (node.next != target) {
//            node = node.next;
//            i++;
//        }
//        return i;
//    }
//
//    public boolean hasCycle(ListNode head) {
//        if (head == null || head.next == null) {
//            return false;
//        }
//        ListNode slow = head;
//        ListNode fast = head.next;
//        while (slow != fast) {
//            if (fast == null || fast.next == null) {
//                return false;
//            }
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//        return true;
//    }

    public ListNode detectCycle(ListNode head)
    {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
            // 如果链表中存在环，就寻找环的入口节点
            if (slow == fast)
            {
                // 将slow节点指向头节点，fast指针位置不变速度变为慢指针速度，再次相遇即为环入口节点
                ListNode p = head;
                while (p != slow)
                {
                    slow = slow.next;
                    p = p.next;
                }
                return p;
            }
        }

        return null;
    }

}
